A Memory-efficient Store for SILT: Part II

Learn how to design a memory-efficient key-value store.

Compact recursive representation#

Trees are generally implemented using pointers. Pointers are required in nodes to store the address of their child nodes. Based on the size and architecture of the underlying hardware, these pointers may be up to eight bytes long. Every internal node will need at least one pointer—this means it isn’t memory-efficient.

We will represent our tries without using pointers. Our representation will essentially be a string containing our compact representation of the prefix tree. This is a recursive representation, meaning we can capture it using a recursive function. The below representation is for our memory-efficient store's in-memory index prefix tree TT with left subtrie LL and right subtrie RR:

Rep(T)=LRep(L)Rep(R)Rep(T) = |L| Rep(L) Rep(R)

where L|L| is the number of leaf nodes in LL. Rep(T)Rep(T) is a special character to indicate an empty or leaf node TT.

The rationale behind using only L|L| is that during a key lookup, if we have to traverse to the right subtree, we will skip all the leaf nodes in the other subtree—the left subtree. Remember that our key-value entries in storage are sorted and stored sequentially, and we use the prefix tree to search our entries in storage. The prefix tree gives us an index. This index is the number of fixed-length entries we will skip to reach our key-value entry, represented by a leaf node in the tree. We will navigate our representation of a tree by counting the number of leaf nodes we have skipped to reach a leaf node. When we reach a leaf node in our representation, our count will give us the index—the number of entries we need to skip in storage to reach our key-value entry. We need to create a compact representation before searching for a key.

Here's our algorithm to create a representation of a trie in Python from an array of sorted keys.

The algorithm above constructs a compact recursive representation for an array of sorted keys. We've used Python strings and not bit-strings for simplicity. Clicking the "Run" button will generate a compact representation of the keys from our example in the illustration from our last lesson—also shown in the slide deck below. Source: "SILT: a memory-efficient, high-performance key-value store", 2011, In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles (SOSP '11).

Note: For simplicity, we have used Python strings. This trie implementation does not allow for indexes greater than nine since it would require two characters. Our implementation should have an array of integers and special characters (or bits) for the leaf node indicator. The latter is to save memory—we only need to indicate a leaf node that does not require 32 bits.

The method to indicate an empty subtree or leaf node depends on the implementation. In our implementation, we have used Python strings for simplicity, and our indicator is the exclamation mark (!).

Running the code above without entering a different K (lines 2–11) yields the result 5421!!1!!!21!!1!1!!. The slide deck below shows how the algorithm provides this value.

Created with Fabric.js 3.6.6
We have entered the sorted keys in storage as an argument to our algorithm. Remember, the tree does not exist in memory. Only the compact representation exists. However, we have used the tree to visualize the creation of the compact representation (top right).

1 of 18

Created with Fabric.js 3.6.6
We start with the root node. There are five keys with 0 as the first bit, and the value of |L| for the root node is 5. Note how there are five leaf nodes in the root's left subtrie. The ellipses in the compact representation are recursive calls for construct(L) and construct(R). These are highlighted in the same color as the root node of the subtree they represent. The first ellipsis (left) represents the call to construct(L), as it comes first in our recursive call. The ellipsis on the right represents the call to construct(R).

2 of 18

Created with Fabric.js 3.6.6
Since the algorithm first made the call to construct(L), we will traverse to the root's left subtrie. This subtrie has four keys with 0 as the second bit, |L| = 4– subtrie's left side has four leaf nodes. Our compact representation will expand where the new ellipses have appeared.

3 of 18

Created with Fabric.js 3.6.6
Traversing left takes us to the subtrie with two keys with 0 as the third bit, |L| = 2; this subtrie's left side has two leaf nodes. The children nodes of this subtrie's root are colored with the highlight color of the ellipses showing where the result of their construct() calls will appear.

4 of 18

Created with Fabric.js 3.6.6
Traversing left takes us to the subtrie with one key with 0 as the fourth bit, |L| = 1; this subtrie's left side has one leaf node.

5 of 18

Created with Fabric.js 3.6.6
Traversing left takes us to our first leaf node, our recursive algorithm's base case. The construct(L) call that brought us here will return "!" and our algorithm adds that to our compact representation. Now the algorithm will execute the construct(R) call in the return statement for this leaf node's parent node.

6 of 18

Created with Fabric.js 3.6.6
We have traversed right because of the construct(R) call and reached another leaf node, so construct(R) will return "!". The return statement for this leaf node's parent node is now complete. Now the algorithm will execute the construct(R) call for the parent's parent node.

7 of 18

Created with Fabric.js 3.6.6
We have traversed right again, and this subtrie has one key with 0 as the fourth bit, |L| = 1; this subtrie's left side has one leaf node. Next, the algorithm will execute the construct(L) and construct(R) calls in the return statement.

8 of 18

Created with Fabric.js 3.6.6
Both the construct() calls are to subtries that are leaf nodes. Both calls return "!".

9 of 18

Created with Fabric.js 3.6.6
Another leaf node and construct(R) returns "!".

10 of 18

Created with Fabric.js 3.6.6
We will traverse right because the construct(L) call for the root node is complete, and the algorithm now executes construct(R). This subtrie has two keys with 0 as the second bit, |L| = 2.

11 of 18

Created with Fabric.js 3.6.6
A subtrie containing one key with 0 as the third bit, |L| = 1.

12 of 18

Created with Fabric.js 3.6.6
Leaf nodes. construct(L) and construct(R) both return "!".

13 of 18

Created with Fabric.js 3.6.6
A subtrie containing one key with 0 as the third bit, |L| = 1.

14 of 18

Created with Fabric.js 3.6.6
This subtrie is a leaf node. Construct (L) returns "!".

15 of 18

Created with Fabric.js 3.6.6
A subtrie containing one key with 0 as the fourth bit, |L| = 1.

16 of 18

Created with Fabric.js 3.6.6
Leaf nodes. construct(L) and construct(R) both return "!".

17 of 18

Created with Fabric.js 3.6.6
Our compact representation is complete. We can access all our keys in storage with a trie index represented by this representation.

18 of 18

5421!!1!!!21!!1!1!! is the compact recursive representation of the of the tree for keys from our example presented in the previous lesson. Let's look at its interpretation given below:

  • 5: This is the value of L|L| for the root node since five keys start with 0, represented by the five leaf nodes in its left subtrie.

  • 4: This is the value of L|L| for root's left child. The four leaf nodes in its left subtrie represent the four keys with 0 in their second position in this subtrie.

  • 2: This is the value of L|L| we get when we go into the left subtrie. There are two keys with 0 in their third position in this subtrie, represented by the two leaf nodes in the subtrie's descendants on the left side.

  • 1!!: The next subtrie in our iteration is the bottom left internal node. The two exclamation marks represent its children nodes, the leaf nodes. We have now finished the left subtries in the root node's left subtrie—one key with 0 in its fourth position in this subtrie's left-side descendants.

  • 1!!: The right subtrie where L|L| equals 2—also the internal node with leaf nodes representing index 2 and 3 as child nodes (denoted by the exclamation marks at the end). One key with 0 in its fourth position in this subtrie's left-side descendants.

  • 21!!1!1!!: This is the compact representation of the root's right subtrie.

While the actual degree of memory saved will vary from system to system, we can try to get an idea of how much memory was saved using this compact representation.

We have ten leaf nodes and eight internal nodes (the root is not an internal node, so we are not counting it). Uniquely identifying 18 nodes requires 5 bits—we can think of this as the memory used by a single pointer, and we need 18 of these. So the total number of bits consumed by pointers is 90 (18 nodes multiplied by 5 bits). Uniquely identifying ten indexes requires 4 bits, and we would need ten of these—these are our indexes stored in the leaf nodes—a total of 40 bits. In total, our in-memory index requires 130 bits without the compact representation.

Note: The reason we have not counted the prefix tree's root node when calculating the total number of bits required to represent a prefix tree is that even the compact representation would require at least one pointer to identify its address. For a prefix tree, this address is generally of the root node.

Our compact representation has required 19 pieces. There are 11 possible values that each piece can take, and it requires 4 bits. We need 19 of these. Hence, the total number of bits consumed is 76. We have saved 54 bits by using the compact representation!

Note: Pointers will require way more than 5 bits, and the pointer-based representation will require much more memory. However, using the compact representation will always save us a significant amount of memory.

Let's look at how we will look up keys in this compact representation.

GET requests#

We will process GET requests in the memory-efficient store to first search the key in the in-memory prefix tree for the key's index. We will then use the index to look up the key in storage. Here is our algorithm to search for a key K in the representation of a trie T.

Algorithm to search for a key in the compact representation of a prefix tree. Like in the previous algorithm, we have used Python strings for simplicity. Source: "SILT: a memory-efficient, high-performance key-value store", 2011, In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles (SOSP '11).

The algorithm recursively navigates T and recurses into the left or right subtree based on K. We first break T into its head (T[0]) and tail (T[1:]). Here are our recursion cases:

  1. The base case is simple. If the head is the special character to indicate a leaf node (exclamation mark in our case), the algorithm returns 0.

  2. If the head does not indicate a leaf node, then we will proceed with the lookup in either of the subtries based on K:

    1. If the first bit of the K is 0, we will proceed with the lookup in the left subtrie with the remaining key K[1:]. The first character in the tail represents the left subtrie. We do not need to add anything to our return value since traversing left does not increase the index.

    2. If the first bit of K is 1, we will proceed with the lookup in the right subtrie with the remaining key K[1:]. We will need to drop the left subtrie to start lookup in the right subtrie—we will do this through our helper function (lines 20–28 in the code snippet above) that is explained below. When returning, we will add the head to our return value since we have skipped the left subtrie by recursing right. The head represents the number of leaf nodes in the left subtrie (L|L| from our representation in the previous section).

Our implementation has a helper function with an algorithm to drop the next left subtrie in our representation T. We first break T into its head (T[0]) and tail (T[1:]). Here are our recursion cases:

  1. The base case is the same as the lookup algorithm. If the head is the special character to indicate a leaf node (an exclamation mark in our case), the algorithm returns 0.

  2. If the head is not the special character, we call the recursive function twice to remove the entire left subtrie.

The slide deck below gives us a step-by-step understanding of how the above algorithm works.

Created with Fabric.js 3.6.6
We will look up the key 01000110 in the compact representation. Like before, remember that the prefix tree does not exist in memory. We are only using it to visualize how our algorithm traverses the prefix tree.

1 of 11

Created with Fabric.js 3.6.6
The first bit is 0, and the head is not "!". We will continue lookup for the remaining key in the tail. Since we did not traverse left, we will not change our return index—the number of leaf nodes skipped, which has also not changed by going left.

2 of 11

Created with Fabric.js 3.6.6
The second bit is 1, and the head is not "!". We will continue to look up the remaining key in the right subtrie. Before we do that, we need to acknowledge that we have skipped some leaf nodes, which has increased our index. The number of leaf nodes that we have skipped is stored in the head so that we will add that to our return value. Next, we will discard the left subtrie—essentially, skip it in the algorithm. After that, we will continue lookup.

3 of 11

Created with Fabric.js 3.6.6
In the first discard call, the head is 2. So we will call the function to discard twice on the tail.

4 of 11

Created with Fabric.js 3.6.6
In the next discard call, the head is 1. Like before, we will call the function to discard twice on the tail. From this point, we have to call it three times.

5 of 11

Created with Fabric.js 3.6.6
The head is "!" in the next discard call. This is the base case, so we do not need to call the function to discard again. The algorithm returns the tail.

6 of 11

Created with Fabric.js 3.6.6
Another "!". We will return the tail.

7 of 11

Created with Fabric.js 3.6.6
In the next discard call, the head is 1. Like before, we will call the function to discard twice on the tail.

8 of 11

Created with Fabric.js 3.6.6
Another "!". We will return the tail.

9 of 11

Created with Fabric.js 3.6.6
Another "!". We will return the tail. And since we do not have to call the discard function again, we have discarded the left subtrie.

10 of 11

Created with Fabric.js 3.6.6
Continued lookup in the tail has brought us to a "!", a leaf node. We have reached our leaf node and will return the number of leaf nodes we have skipped to get here: 4.

11 of 11

We can see in the above slide deck (slide 3) that at the time of traversing to the right subtrie, we have added the value of L|L| of the node at which we traverse right. The value of L|L| gives us the number of leaf nodes we skipped while traversing right—the number of nodes in the left subtrie.

A Memory-efficient Store for SILT: Part I

A Memory-efficient Store for SILT: Part III